package someTestExcemple.huaweiOd.string;
import java.util.*;
//华为OD机试 - 最小循环子数组（Java 2023 B卷 100分）
//https://blog.csdn.net/guorui_java/article/details/131721023
public class CircularSubarrayKMP {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取数组元素个数
        int n = scanner.nextInt();
        int[] nums = new int[n];
        // 读取数组元素
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        // 调用 findSmallestRepeatingSubarray 方法找出最小重复子数组
        int[] result = findSmallestRepeatingSubarray(nums);
        // 输出最小重复子数组
        for (int i = 0; i < result.length; i++) {
            if (i > 0) {
                System.out.print(" ");
            }
            System.out.print(result[i]);
        }
        scanner.close();
    }

    public static int[] findSmallestRepeatingSubarray(int[] nums) {
        int n = nums.length;
        // 将数组转换为字符串
        StringBuilder sb = new StringBuilder();
        for (int num : nums) {
            sb.append(num);
        }
        String str = sb.toString();

        // 计算前缀表
        int[] next = computeNext(str);
        System.out.println("next[]==>" +Arrays.toString(next));
        //可能最小重复字串的长度
        int len = n - next[n - 1];
        /**
         * 6
         * 1 2 1 2 1 2
         * next[] ==>[0, 0, 1, 2, 3, 4]
         */
//        1. 最长公共前后缀与重复子串的关系
//        假设存在一个字符串 S，它由某个子串 T 重复 k 次构成，即 S = T * k（k 为正整数）。
//        当我们计算字符串 S 的前缀表 next 时，next[n - 1]（n 是 S 的长度）表示的是 S 的最长公共前后缀的长度。由于 S 是由 T 重复构成的，那么这个最长公共前后缀其实是由多个完整的 T 组成。
//        设 S 的前 x 个字符和后 x 个字符构成最长公共前后缀（即 next[n - 1] = x），
//        可以发现 S 去掉这个最长公共前后缀后剩下的部分就是最小重复子串 T。所以，最小重复子串的长度就等于 n - next[n - 1]。
        //得出结论：在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串。
        //todo 即-->如果字符串由重复字串组成，最小重复字串长度：len=n-next[n-1]
        if (n % len == 0) {
            int[] subarray = new int[len];
            for (int i = 0; i < len; i++) {
                subarray[i] = nums[i];
            }
            return subarray;
        }
        //只能自己做重复字串
        return nums;
    }

    //todo 计算next数组--牢记
    //"abcadc"
    private static int[]   computeNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        int j = 0;
        for (int i = 1; i < m; i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
